package com.cn.codebrush.动态规划;

/**
 * @Author Boolean
 * @Date 2022/5/16 10:54
 * @Version 1.0
 */
public class No494目标和 {
    public static void main(String[] args) {
        int[] nums1 = {2,107,109,113,127,131,137,3,2,3,5,7,11,13,17,19,23,29,47,53};
        int[] nums2 = {1,1,1,1,1};
        System.out.println(findTargetSumWays(nums1,1000));
    }

    public static int findTargetSumWays(int[] nums, int target) {
        int n = nums.length;
        int sum = 0;
        for(int num:nums){
           sum += num;
        }
        if((sum-target)%2 != 0){
            return 0;
        }
        int val = (sum-target)/2;
        if(val < 0){
            return 0;
        }
        int[] dp = new int[val+1];
        dp[0] = 1;
        for(int num:nums){
            for(int i=val;i>=num;i--){
                dp[i] += dp[i-num];
            }
        }
        return dp[val];
    }
}
